// 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
// 你可以对一个单词进行如下三种操作：
// 插入一个字符
// 删除一个字符
// 替换一个字符
// 示例 1：
// 输入：word1 = "horse", word2 = "ros"
// 输出：3
// 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
// 1. 确定dp数组以及下标的含义，`dp[i][j]`，表示下标为i-1的word1和下标为j-1的word2,最近编辑距离
// 2. 确定递推公式
//     1. 如果`word1[i-1] === word2[j-1]`，不用任何编辑，`dp[i][j] = dp[i-1][j-1]`
//     2. 如果`word1[i-1] !== word2[j-1]`
//         1. 删除word1一个元素，`dp[i-1][j] + 1`
//         2. 删除word2一个元素，`dp[i][j-1] + 1`
//         3. 替换元素，`d[i-1][j-1] + 1`
//         4. `dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)`
// 3. 初始化

function minDistance(word1, word2) {
    let dp = new Array(word1.length + 1).fill(0).map(_ => new Array(word2.length + 1).fill(0))
    for (let i = 0; i <= word1.length; i++) {
        dp[i][0] = i
    }
    for (let j = 0; j <= word2.length; j++) {
        dp[0][j] = j        
    }
    for (let i = 1; i <= word1.length; i++) {
        for (let j = 1; j <= word2.length; j++) {
            if (word1[i-1] === word2[j-1]) {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)
            }
        }        
    }
    return dp[word1.length][word2.length]
}
let word1 = "horse", word2 = "ros"
console.log(minDistance(word1, word2))